import copy


class Graph:
    __name = 'Graph'

    ''' 无向图是否是连通图（广度优先遍历） '''

    @staticmethod
    def ug_is_connected(g=None):
        if g is None:
            return False

        v_set = g[0]  # 图的点集
        s_set = list(g[1].keys())  # 图的边集名，不用考虑权重

        tree = [v_set[0]]  # 树的结点集
        v_set_new = [v_set[0]]  # 新增节点集

        while True:
            v_con = copy.deepcopy(v_set_new)  # 加入需要遍历的点集
            v_set_new = []  # 初始化新增节点集合
            for v in v_con:  # 遍历当前深度的点集合
                for s in copy.deepcopy(s_set):  # 遍历边集合
                    if v in s:  # 找到关联的边
                        vc = s.strip(v)  # 联通点
                        if vc not in tree:  # 联通点未在树中
                            tree.append(vc)  # 树中加入联通点
                            v_set_new.append(vc)  # 加入新增节点集
                        s_set.remove(s)  # 边集中删除边
            if len(v_set_new) == 0:
                break
        return len(tree) == len(v_set)  # 连通时生成树的节点数应该等于图的节点数
